{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Trim a Binary Search Tree \n",
    "\n",
    "## Problem Statement\n",
    "\n",
    "Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree. So, if we get this tree as input:\n",
    "___\n",
    "\n",
    "![title](bst1.png)\n",
    "___\n",
    "and we’re given **min value as 5** and **max value as 13**, then the resulting binary search tree should be: \n",
    "___\n",
    "![title](bst_trim.png)\n",
    "___\n",
    "We should remove all the nodes whose value is not between min and max. \n",
    "\n",
    "___\n",
    "** Feel free to reference the lecture on Binary Search Tree for the node class, but what it more important here is the logic of your function. In which case your function should be in the form:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 669. Trim a Binary Search Tree\n",
    "class Solution:\n",
    "    def trimBST(self, root, min_val, max_val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type min_val: int\n",
    "        :type max_val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val < min_val:\n",
    "            return self.trimBST(root.right, min_val, max_val)\n",
    "        if root.val > max_val:\n",
    "            return self.trimBST(root.left, min_val, max_val)\n",
    "        root.left = self.trimBST(root.left, min_val, max_val)\n",
    "        root.right = self.trimBST(root.right, min_val, max_val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** There is no solution cell because the nature of the code should be more logical and a test would essentially give away the answer. Just focus your answer to fill out the logic of the solution using the methods described above **\n",
    "\n",
    "## Best of luck!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
